\subsection{Analysis of \symdiff\ starting from well-mixed distributions}
\label{sec:sym_diff_analysis}

For the proof of Theorem~\ref{thm:rand_sym_diff}, we will assume that
we start from the initial token distribution where each node has each
token independently with probability $\frac{1}{2}$.  It is easy to
extend it to any positive constant probability.  We need the following
definition. We call a maximal set of nodes that holds the same set of
tokens at the start of a round $r$ to be a {\em group} for round $r$.

\begin{lemma}
\label{lem:sym_diff_groupsize}
In a token distribution where each node has each token independently
with probability $\frac{1}{2}$, the union of the set of tokens of any
$\ell$ nodes misses at most $\frac{n+k}{\ell}$ tokens with high
probability.
\end{lemma}

\iflong
\begin{proof}
There are ${n \choose \ell}$ ways of choosing $\ell$ nodes out of $n$
nodes, and ${k \choose \frac{n+k}{\ell}}$ ways of choosing
  $\frac{n+k}{\ell}$ tokens out of $k$ tokens. Thus the probability
  that the union of the set of tokens of any $\ell$ nodes misses
 more than $\frac{n+k}{\ell}$ tokens is at most
\[ {n \choose \ell} {k \choose \frac{n+k}{\ell}} \left(\frac{1}{2}\right)^{n+k}, \]
which is inverse polynomial in both $n$ and $k$.
\end{proof}
\fi

Since in any round, no token can be exchanged along an edge between
two nodes of the same group, we will consider only the edges that
connect two nodes from different groups. We call such edges {\em
  inter-group} edges for that round. In fact, we will prove the
theorem in a stronger sense where we let the adversary orient the
inter-group edges to determine the direction of token movement
along all these edges, and the token sent along each of these edges is
chosen uniformly at random from the symmetric difference conditioned
on this orientation. (The adversary must respect the condition that
there can be no token movement from a node $u$ to a node $v$ if the
set of nodes held by node $u$ is a subset of that held by node $v$.)
We define one unit of progress in a round as a node receiving a token
in that round that it did not have at the start of the round.

\begin{lemma}
\label{lem:sym_diff_progress}
With high probability, the following holds for every node $v$ and
every round $i$: If $v$ misses $m > \log n$ tokens at the start of
round $i$ and it has $d > \log k$ incoming inter-group edges in that
round, then node $v$ makes $\Omega(\min\{m,d\})$ units of progress in
round $i$. Here, the probability is over the initial token
distribution and the randomness used in the protocol.
\end{lemma}
\iflong
\begin{proof}
First we prove the claim that that for some sufficiently small
constant $\alpha < 1$, with probability $1-o(1)$, the following holds
for every node $v$ and every round $i$: If $v$ misses $m > \log n$
tokens at the start of round $i$ and it has $d > \log k$ in-neighbors
in that round, then $\alpha d$ of these neighbors each have, at the
start of round $i$, $\alpha m$ tokens that node $v$ misses. Let us
compute the probability that the claim is not true for some node $v$
in some round $i$. The $d$ inter-group in-neighbors can be chosen in
at most ${n \choose d}$ different ways and the $m$ missing tokens can
be chosen in at most ${k \choose m}$ different ways. There are at most
${d \choose \alpha d}$ ways of choosing the in-neighbors that do not
have the claimed number of missing tokens, and for each of them there
are at most ${m \choose \alpha m}$ ways of choosing which of these
tokens they miss. Thus the probability of failure is at most
\[ {n \choose d} {k \choose m} {d \choose \alpha d} {m \choose \alpha m}^{(1-\alpha)d} \left(\frac{1}{2}\right)^{(1 - \alpha)^2 md}, \]
which is $o(\frac{1}{(nk)^2})$ since $m > \log n$ and $d > \log k$ and
$\alpha$ is chosen sufficiently small. Noting that there are at most
$n$ choices for $d$ and at most $k$ choices for $m$, the claim
follows. From the above claim, the lemma follows by standard
calculations.
\end{proof}
\fi

\begin{proof}[Proof of Theorem~\ref{thm:rand_sym_diff}]
We color each of the rounds {\em red}, {\em blue}, {\em green} or {\em
  black}. If in a round, there is a node $v$ that misses less than
$\log n$ tokens and makes at least one unit of progress in that round,
we color the round red. If a round is not colored red, and there is a
node that gets a constant fraction of its missing tokens in that round
(the same fraction as in Lemma~\ref{lem:sym_diff_progress}), we color
it green. If a round is neither colored red nor colored green, we
color the round blue. \junk{It is clear from
  Lemma~\ref{lem:sym_diff_groupsize} and
  Lemma~\ref{lem:sym_diff_progress}, that with probability $1 - o(1)$,
  we will be able to color all the rounds red, green or blue till the
  protocol completes $k$-gossip. Thus we just need to bound the number
  of red, green and blue rounds.}

It is immediate that there can be at most $n \log n$ red rounds since
each of the $n$ nodes can be responsible for coloring at most $\log n$
rounds red. Similarly, there can be at most $O(n \log k)$ green rounds
since each node can be responsible for coloring at most $O(\log k)$
rounds green. Now let us turn to the blue rounds. Fix a blue round and
let there be $r$ groups in that round. Using
Lemma~\ref{lem:sym_diff_groupsize}, we infer that there are at most
$(n+k)r$ tokens missing in total at the start of this round. We also
note that there must be at least $r-1$ inter-group edges in this round
and combining this with Lemma~\ref{lem:sym_diff_progress} and the fact
that this round was not colored red or green, we infer that we make
$\Omega(\frac{r}{\log k})$ units of progress in this round.

We can label each blue round by the smallest number of groups in a
blue round seen so far. The sequence of labels is non-increasing and
let us say it starts from $s \leq n$. We divide the blue rounds in
partitions where the $i$'th partition contain those with labels in
$[s/2^{i-1},s/2^i)$. There are at most $\log n$ partitions. From the
  above argument, we see that there can be at most $O((n + k)\log k)$
  blue rounds in each partition, which implies a bound of $O((n+k)
  \log n \log k)$ for the total number of blue rounds. This completes
  the proof of the theorem.
\end{proof}
